home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Libris Britannia 4
/
science library(b).zip
/
science library(b)
/
MATH
/
LP261.ZIP
/
LP.MAN
< prev
next >
Wrap
Text File
|
1993-07-21
|
64KB
|
2,178 lines
Note: This text may not be 100% suitable for all printers.
ScanSoft(tm)
LP
Linear Programming Optimizer
Version 2.61
(C)1988-1993 Cornel Huth
LP OPERATIONS MANUAL --------------------------------------
[OVERVIEW]
LP is a linear programming optimizer developed for either
maximizing or minimizing small to medium sized mathematical
programming problems in which all the relationships between
variables are linear. It finds a BEST feasible solution to
any continuous, integer, or mixed-integer optimization problem
of this type and reports on the activities and levels required
to maximize profit or minimize cost. LP also reports on
alternate optima, shadow prices, ranges over which the shadow
prices are valid and ranges over which profit/cost inputs and
right-hand-side (RHS) values can vary without altering the
solution.
LP can use either LOTUS 1-2-3/Symphony spreadsheet files or
ASCII files for data input. Output may be sent to most
printers, any ASCII disk file, or directly to a LOTUS 1-2-3
spreadsheet file. Output may consist of useful model debugging
information such as objective function and constraint listings,
a condensed matrix map, and the full tableaux. LP handles
problems with thousands of variables and thousands of con-
straints.
[INPUT FILE]
LP reads a user created file for data input. Any text
editor or word processor that can output unformatted ASCII
text may be used. LOTUS 1-2-3 or Symphony (or any 1-2-3
compatible spreadsheet such as VP-Planner or Excel) can be
used for creating the data file, as well.
A batch facility is available in LP. This allows LP to
solve up to six LP problems per run without the need of using
DOS's COMMAND batch facility. Such a file is to include only
the LP filenames followed by any command line options and
should contain no blank lines. To specify a batch file to
LP, precede the filename with an @ on the command line.
E.g., if the batch file is named BATCHRUN.BLP, use C>LP
@BATCHRUN.BLP.
NOTE: The length of any one line should not exceed 2300
characters.
2
LP OPERATIONS MANUAL --------------------------------------
- EXAMPLE
TITLE: An example of an LP data file.
OUTPUT: EXAMPLE.OUT
LISTING: YES
MAP: YES
TABLEAU: YES
ANALYSIS: YES * anything after a '*' on a line is a comment
VAR: 3 LTE: 2 GTE: 0 EQU: 1
FUNCTION: MAX: .185 stock + .090 bond -.150 loan
MxLoan loan <= 5000 * no coefficient implies 1.00
MxStk stock <= 4000
MxCash stock + bond - loan = 10000
END:
NOTE: It is not neccesary to use + operators between variables,
e.g.,
...MAX: .185 stock .090 bond -.150 loan is acceptable, as
is
...MAX: +.185 stock +.090 bond + -.150 loan.
3
LP OPERATIONS MANUAL --------------------------------------
[STARTING LP]
To give LP a go, have LP.EXE in your PATH and EXAMPLE.LP
in the current directory, then type:
C>LP EXAMPLE.LP
In just a few seconds it's finished. Now do (printer on?):
C>COPY EXAMPLE.LP PRN
... then do (you may want to advance the printer to the
top-of-page):
C>COPY EXAMPLE.OUT PRN
The file EXAMPLE.LP is the data file that LP used and
EXAMPLE.OUT is the file that LP created for the output.
If you do not have a printer, have LPEDIT.COM in your PATH and
EXAMPLE.OUT in the current directory, then type:
C>LPEDIT EXAMPLE.OUT
4
LP OPERATIONS MANUAL --------------------------------------
[LINE OPTIONS]
/B use with non-color composite displays connected
to color card
/C:nnn specify the attribute for color screens
(fg+(bg*16)) <=255
- the above switches have no effect within LP batch files
/O:filename specify the output destination (can include
drive/path)
/I:nn specify all-integer solution max of nn cutplanes
(nn=0-99)
/M:nn specify mixed-integer solution max of nn cutplane
(nn=0-99)
/Z:nn specify tolerance of zero (nn=.000000000001-.9)
/PL:OFF suppress printer page length codes (page length
from 88 to 66)
/PW:OFF suppress printer page width code (for 15"
printers)
/FF:OFF suppress all form feeds except at end of report
/L or /NL turn listing on or off (/Nx turns switch off)
/MA or /NM turn map on or off
/T or /NT turn tableaux on (first and last only) or off
/A or /NA turn analysis on or off
/VM use with problems too large for DOS memory
C>LP EXAMPLE.LP /O:PRN /NL /NM /NT /NA /C:31
5
LP OPERATIONS MANUAL --------------------------------------
[COMMENTS]
COMMENTS can be used in an LP data file. They may appear
anywhere except on the TITLE: line. To include comments in
the input file, begin the comment with an asterisk. All
characters following the * to the end of that line are skipped.
E.g.,
* LP data file for BUDGETING 1990 MODEL A1B.
VAR: 233 * the constraints & variables were developed
LTE: 35 * jointly by the OR & MIS departments
GTE: 55 *
EQU: 22
[KEYWORDS]
Keywords are used to declare the problem to LP. All
keywords in LP end with a colon.
TITLE: Trial MX01 * this is optional
VAR: 52 LTE: 22 GTE: 44 EQU: 0 * these are required
FUNCTION: MAX: 59.03 var1 + 35.57 var2 * these are required
Keywords may be either upper or lower case.
- TITLE:
TITLE: is an optional keyword. Its purpose is to allow the
user to specify the title used for each page heading. The
keyword NAME: may be used interchangably with TITLE:, e.g.,
TITLE: Operations Research Planning Model 20A or,
NAME: Operations Research Planning Model 20A
If TITLE: or NAME: is not used, the input filename is used by
default.
NOTE: Only the first 48 characters following TITLE: will be
used. Comments should not appear on the comment line.
6
LP OPERATIONS MANUAL --------------------------------------
- OUTPUT:
OUTPUT: is an optional keyword. Its purpose is to allow the
user to specify which device the output is to be sent. To send
the output directly to the printer, use PRN after OUTPUT:,
e.g.,
OUTPUT: PRN * or any valid DOS device name (\DEV\devicename)
To send the output to disk, indicate the pathname after
OUTPUT:, e.g.,
OUTPUT: C:\OR\B90\MODEL20A.OUT
To send output in LOTUS 1-2-3 WKS format, specify a filename
extension of WKS, e.g.,
OUTPUT: C:\123\MODEL20A.WKS
NOTE: Only the analysis and solution sections are in 1-2-3
format; the listings, map, and tableaux are in ASCII format and
will be overwritten if there are no errors in the data file.
If OUTPUT: is not used, the input filename.OUT is used by
default.
- LISTING:
LISTING: is an optional keyword. Its purpose is to allow the
user to specify if listings of the objective function and
constraints are to be output.
The listing numbers each objective function variable, showing
its name and coefficient and whether the objective is to
maximize or minimize the function.
For each constraint, its name, matrix row position, and the
coefficient and name of the non-zero variables and the value of
the RHS is given. The LTE's fill from row 1 down, GTE's fill
from the last GTE up, EQU's fill from the last GTE+1 down in
the matrix (to handle negative RHS's). If the RHS of a
constraint is negative, an N precedes its name. It will have
been multiplied through by -1 and the type changed if an
inequality.
To activate the listing, use YES. For no listing use NO.
E.g.,
LISTING: YES * If LISTING: is not used, NO is used by default.
7
LP OPERATIONS MANUAL --------------------------------------
- MAP:
MAP: is an optional keyword. Its purpose is to allow the user
to specify if a mapping of the initial matrix is to be output.
The map is shown in condensed form with variable names output
vertically and the constraint names along the left.
For each matrix position a symbol is used to indicate in which
range that value is. For instance, all zero elements show as
blanks, all one elements as 1, greater than 1 but less than 10
as W, and so on.
To activate the mapping, use YES. E.g.,
MAP: YES * If MAP: is not used, NO is used by default.
NOTE: The matrix fills from the top down for LTE's and from
the bottom (actually right before the first EQU) up for GTE's.
- TABLEAU:
TABLEAU: is an optional keyword. Its purpose is to allow the
user to specify if tableaux are to be output. The tableau that
is output is of the last iteration completed.
The objective function variables and values are listed. The
variables in the current basis along with their row elements
and RHS's follow. A Z follows the objective function evalua-
tion and an R follows each of the RHS values.
To activate tableau output of the initial and last tableaux
only, use YES, or I&L. To output all tableaux, use ALL. E.g.,
TABLEAU: YES * or TABLEAU: I&L
* or, for all,
TABLEAU: ALL * If TABLEAU: is not used, NO is used by default.
- ANALYSIS:
ANALYSIS: is an optional keyword. Its purpose is to allow the
user to specify if an analysis of the solution is to be output.
The analysis is divided into two summaries.
In the variable summary, each variable name, alternate optima
check, activity level, shadow price, input coefficient, and
range over which the input coefficient may vary without
8
LP OPERATIONS MANUAL --------------------------------------
altering the solution set is given. Also shown is the variable
ENTERING the basis when this range is exceeded.
In the constraint summary, each name, type, unused capacity/-
excess demand, shadow price, input RHS, and range over which
the RHS may vary without altering the solution set is given.
Also shown is the variable EXITING the basis when this range
is exceeded.
To activate analysis output, use YES. E.g.,
ANALYSIS: YES *If ANALYSIS: is not used, YES is the default.
- BIG-M:
BIG-M: is an optional keyword. Its purpose is to allow the
user to specify the objective function coefficient given to
artificial variables.
LP uses the BIG-M improved SIMPLEX algorithm. Starting the
SIMPLEX algorithm requires an artificial variable for the GTE:
with the largest RHS and one for each EQU: constraint. To
ensure that the algorithm removes these as quickly as possible
from the basis, a very large value is given it. BIG-M: allows
the user to specify this value.
NOTE: In minimization problems, values in the objective
function are interpreted as contributions to cost. Thus,
absolute values should be used, i.e., 37.6667 MAT123 for the
contribution to cost of MAT123.
To specify BIG-M: use the absolute value after the keyword.
E.g.,
BIG-M: 1000000 * If BIG-M: is not used, 1,000,000 is default.
* 1D+006 may be used instead of 1000000.
- TZERO:
TZERO: is an optional keyword. Its purpose is to allow the
user to specify a tolerance value for zero.
LP, like most computer software, deals with numbers in a
finite precision. In repeated manipulations of numbers that
have been truncated to a specific precision, round-off errors
may occur. TZERO: allows for this somewhat in critical areas
9
LP OPERATIONS MANUAL --------------------------------------
by forcing the algorithms and output routines to interpret very
small values near 0.00 as 0.00.
LP uses IEEE double-precision floating-point numbers. With
an 80x87 math coprocessor, very fast and precise computations
are made. If an 80x87 is not installed, software emulation is
used.
To specify TZERO: use the absolute value after the keyword.
E.g.,
TZERO: 1D-012
* If TZERO: is not used, 1D-012 is default.
* .000000000001 may be used instead of 1D-012.
* If INTEGER:/MIXED:, .00001 is used unless /Z: is used.
- INTEGER:
INTEGER: is an optional keyword. Its purpose is to allow the
user to specify that an all-integer solution is to be sought.
LP uses a cutplane algorithm to solve an all-integer
problem. All constraint coefficients/RHS should be integer.
The maximum number of cutplanes that will be used to find a
solution is to follow the keyword INTEGER:. The range is from
0 to 99. If the maximum number of cutplanes is reached, LP
exits and uses the current solution.
NOTE: If the cutplane technique is going to find a solution, it
generally does so quickly. The range analysis will not be
valid since it is calculated for continuous ranges. EQU
constraints cannot be analyzed. The memory requirement
increases by one constraint and variable for each cutplane
requested. Because rounding errors are more pronounced, TZERO:
is set to .00001. This can be changed only with /Z:. Solu-
tions cannot be guaranteed. This feature should be used only
for small problems.
- MIXED:
MIXED: is an optional keyword. Its purpose is to allow the
user to specify that a mixed-integer solution is to be sought.
LP uses a cutplane algorithm to solve a mixed-integer
problem. Any integer constraint should have integer coeffi-
cients and RHS. The maximum number of cutplanes that will be
10
LP OPERATIONS MANUAL --------------------------------------
used to find a solution is to follow the keyword MIXED:. The
range is from 0 to 99. If the maximum number of cutplanes is
reached, LP exits and uses the current solution.
To specify a decision variable or slack (or surplus) variable
to have an integer value in the solution, begin the decision
variable or constraint name with a CAPITAL letter between I
and N (I,J,K,L,M,N).
The notes for INTEGER: apply to MIXED:.
- VAR: LTE: GTE: EQU:
VAR:, LTE:, GTE:, EQU: are all required keywords. VAR:
declares the number of decision variables in the model. LTE:,
GTE:, and EQU: declare the number of less-than-equal-to,
greater-than-equal-to, and equal-to constraints, respectively.
E.g.,
VAR: 22
LTE: 5 * 3 of these LTE: constraints have negative RHS's
GTE: 3
EQU: 2
NOTE: If the RHS of an LTE: or GTE: is negative, the LTE: or
GTE: number will be adjusted by LP, e.g., there are 5 LTE:'s
and 3 GTE:'s, yet 3 LTE:'s have negative RHS's. LP will
transform those 3 LTE:'s to GTE:'s and adjust the LTE: number
to 2 and GTE: to 6.
- FUNCTION:
FUNCTION: is a required keyword. FUNCTION: is to mark the
start of the problem definition portion of the model.
- MIN: MAX:
MIN: and MAX: are required keywords, though only one may be
specified. MIN: indicates to LP that the objective function
following is a cost function that is to be minimized; MAX:
indicates that the function is a profit function that is to be
maximized.
11
LP OPERATIONS MANUAL --------------------------------------
- END:
END: is an optional keyword. Its purpose is to indicate the
end of the problem definition portion of the model. Any data
following END: is not used.
This keyword is useful if the model is to be extensively
documented. All comments that appear before END: will slow the
parsing process. Therefore, extensive comments should appear
after the END: keyword.
NOTE: END: must have nothing else on its line.
[OBJECTIVE FUNCTION]
The objective function contains variables and coefficients
to those variables representing the variable's profit or
cost. The coefficients used normally should be positive for
both profit and cost problems; the values are interpreted
accordingly by specifing MIN: or MAX:. If, however, in a
profit function a cost is associated with a variable, then that
variable's coefficient should be negative. Likewise in a cost
function, if a profit is associated with a variable, its
coefficient should be negative.
All decision variables (number following VAR:) in the problem
must be in the objective function, including those with
coefficients equal to zero (so that LP can later recognize
them). E.g.,
FUNCTION: MAX: 10 VAR01 + 15.59 VAR02 + 0 VAR03 - VAR04+...
[VARIABLES]
Variables are used in linear programming problems to represent
an activity of an operation. Only decision variables (number
following VAR:) are to be input to LP. Slack, surplus, and
artificial variables of the constraints are created by LP,
as needed. These variables take the name of their constraint
and are preceded by a - for slack, + for surplus, and ! for
artificial variables.
Each variable may be up to six characters (the first being a
letter) and must be unique, as must variables within con-
straints, i.e., don't have two identical variable names in the
same constraint. LP has error detection and reporting
schemes to indicate these type errors.
12
LP OPERATIONS MANUAL --------------------------------------
Any variable not preceded by a coefficient is given a value of
1.00.
NOTE: Do not use + or - in a variable name nor use E or D alone
as a variable name (it would then be interpreted as a number).
[CONSTRAINTS]
Constraints are used in linear programming problems to repre-
sent limitations to the objective function. For each less--
than-equal-to (LTE) constraint, LP adds to the objective
function a slack variable that is named as the constraint,
preceded by a -, and has a coefficient of 0. For each GTE
constraint, a surplus variable is added, preceded by a +,
with a coefficient of 0. In addition, one artificial variable
is added for the GTE with the largest RHS, preceded by a ! and
a coefficient of BIG-M. For each EQU an artificial variable,
preceded by a ! and a coefficient of BIG-M, is added.
The number of each type of constraint is indicated in the
declaration portion (LTE:, GTE:, EQU:).
Constraints may be entered in any order, but LTE, GTE, EQU is
recommended.
Each constraint is to be named (as the variables are), should
include only the non-zero variables, and end with the RHS value
preceded by the corresponding relational operator (<=, >=, =).
E.g.,
CON001 5X11 -X22 <= 5000.
- SLACK
For each LTE constraint in the linear programming problem,
LP adds a slack variable. This slack variable is to
represent the amount of unused capacity. If, for instance,
the total number of hours available for use of a machine is
280 per month, then if in the optimal solution the total hours
for that machine is 260, then 20 hours is unused, or slack.
This slack capacity has an associated shadow price which
indicates the rate of change of the value of the objective
function when the available resource (capacity) varies. (If
there is unused capacity then the value of additional capacity
is 0.00, of course.) This shadow price is valid only over
13
LP OPERATIONS MANUAL --------------------------------------
the range of optimality for that variable. If one unit more
were available, profit would increase (cost would decrease) by
the shadow price; if one less unit were available, then profit
would decrease (cost increase).
A shadow price of zero is given to a slack variable in the
final solution and also to any alternate optima.
A slack variable is named for its constraint, is preceded by a
-, and has an objective function coefficient of 0.
- SURPLUS
For each GTE constraint in the linear programming problem,
LP adds a surplus variable. This surplus variable is to
represent the amount in excess of demand. If, for instance,
the total number of desks needed by contract is 100 per month,
then if in the optimal solution, the total desks to be produced
that month is 105, an excess, or surplus, or 5 desks exists,
relative to the contract constraint.
This surplus demand has an associated shadow price which
indicates the rate of change of the value of the objective
function when the requirement (demand) varies. This shadow
price is valid only over the range of optimality for that
variable. If one unit more were required, profit would
increase (cost would decrease) by the shadow price; if one less
unit were required, then profit would decrease (cost increase).
A shadow price of zero is given to a surplus variable in the
final solution and also to any alternate optima.
A surplus variable is named for its constraint, is preceded by
a +, and has an objective function coefficient of 0.
- ARTIFICIAL
For each EQU constraint in the linear programming problem,
LP adds an artificial variable. For the GTE constraint with
the largest RHS, LP adds an artificial variable. The other
GTE constraints are temporarily transformed into LTE con-
straints by multipling through by -1.
This is a requirement for starting the SIMPLEX algorithm. If
there are no GTE constraints, a dummy artificial variable is
added, nonetheless.
14
LP OPERATIONS MANUAL --------------------------------------
An artificial variable is named for its constraint, is preceded
by a !, has an objective function coefficient of BIG-M and, if
in the final solution, must have an activity level of zero.
NOTE: If an artificial variable of a redundant equality
constraint occurs in the solution with an activity level of
zero, the sensitivity analysis and shadow prices may have been
grossly misstated. Therefore, it is suggested that those
equality constraints with artificial variables in the final
solution (indicated by a !) be removed from the model or
changed to a GTE and the model run again.
[DISPLAY SCREEN]
Date, time, coprocessor status(87 or EmuLATION)/speed index-
(PC=1.0), virtual memory status, and available memory remaining
are shown on top line.
The FILES In/Out display the rightmost 20 characters of the
filenames. OPTIONS displays the status of the output switches.
If degeneracy is detected, DEGENERATE is displayed below PROFIT
EVALUATION.
INTEGER, MIXED, BIG-M, and TZERO are displayed.
Constraint and variable counts are displayed.
The SIMPLEX STATUS indicates the time the SIMPLEX algorithm was
entered and its estimated finish.
Iterations equals SIMPLEX pivots.
Elapsed time is actual time spent in SIMPLEX (which excludes
tableau output and cutplane formulation).
PROFIT EVALUATION is the function value at the current
iteration.
FILE DISPOSITION lists files in queue. The status of the
current file is continually displayed.
[OUTPUT]
The output may be sent either to a disk file or directly to a
printer. Output may include the problem definition listings,
15
LP OPERATIONS MANUAL --------------------------------------
a condensed matrix map, tableaux, and solution analysis in
addition to the final solution.
ASCII output is formatted to 132 columns and a page break is
generated for each page with appropriate section headings.
Beginning each output are the necessary printer control codes
for the 132 column output and 88 lines/page. Ending each
output are the codes to restore the printer to normal. These
codes are EPSON compatible printer codes and work with the most
dot-matrix printers.
Disk output may be edited by any ASCII text editor, imported to
wordprocessor programs, or sent directly to a WKS spreadsheet
file.
NOTE: Make sure that sufficient disk space is available if
output is directed to disk - especially a 360KB floppy.
- LISTING SECTION
The listing section is the LP interpretation of the data
file. The data in this section is the actual data used by the
program. If LISTING: has been requested then the objective
type (maximization or minimization), the number of variables,
and the variables and coefficients are displayed, 4 per line.
The constraints follow.
For each of the constraints, the name, row position in the
initial tableau, coefficient and name for non-zero variables is
output followed by the operator (<=, >=, =) and RHS. If the
RHS was negative, an N precedes this.
If LP detects an error, such as a duplicate variable name,
and listing has been requested, then the error message is
output at the point of the error. If no listing has been
requested, the error message alone is output.
- MAP SECTION
The map section contains a condensed listing of the initial
matrix including the decision variables and constraints. Atop
each map section page a legend of the symbols used is shown.
The map heading showing the variable names follows. The
objective function and variable symbols are next, and for each
constraint, its type, name, initial variable coefficients,
plus RHS value, are shown.
16
LP OPERATIONS MANUAL --------------------------------------
The map is useful for debugging. It can show most wildly-off
data entries, as well as positional type errors.
NOTE: If output to a printer, the map should extend no more
than the columns available with the printer. Printers with 132
columns can print up to 60 variables/line before the following
data wraps to the next line. Many text editors allow column
widths of 512 characters or more. With such an editor, the map
can be displayed without the confusing wrap-around.
- TABLEAU SECTION
The tableau section contains the objective function, its
evaluation, the basic variables, matrix coefficients, and RHS's
at that particular tableau. Either the initial and last
tableaux or all tableaux may be output, depending on TABLEAU:.
The tableaux can be used for debugging. It is a detailed
version of the matrix map, and is available at every iteration,
whereas the map is available for the initial tableau only. It
also can display all the variables without wrap-around problems
since it formats the output for 8 variables per line, using as
many lines as are necessary.
For ease of spotting, a Z follows the objective function
evaluation, and an R follows every RHS.
The SIMPLEX algorithm as implemented in LP always solves the
problem as a maximization type. Minimization problems have the
original objective function multiplied through by -1. This
will in no way affect the outcome. It is mentioned here since
the label MAXIMIZE is at the beginning of each tableau.
- ANALYSIS SECTION
The analysis section contains a wealth of information that the
user will find extremely useful. This section is divided into
two sections, the variable summary, and the constraint summary.
Within the variable summary (for each variable) an indication
is given if that variable is an alternate optima, the activity
level of that variable (blank if not in the solution), its
shadow price, and a sensitivity analysis (or range of optimal-
ity) of the input coefficient. This ranging indicates the
lower and upper values that the input coefficient may take,
everything else remaining the same, and not alter the solution
set (activities and levels of the solution). Where a range is
17
LP OPERATIONS MANUAL --------------------------------------
exceeded, the name of the variable ENTERING the basis is given
(though not necessarily the final solution).
In the constraint summary for each constraint, its type, amount
of slack/surplus, shadow price, and range of optimality for the
RHS value is given. Where a range is exceeded, the name of the
variable EXITING the basis is given.
- SOLUTION SECTION
The solution section is the bottom line of the linear program-
ming problem. It indicates a set of variables and activity
levels that optimizes the objective function given the con-
straints.
The objective function evaluation is the first entry in this
section and equals the optimal profit or cost. Each of the
solution variables, its associated activity level, input
coefficient, and extended amount (of profit or cost) follow.
NOTE: The FUNCTION activity level represents the optimal value
of the profit function (maximize) or cost function (minimize).
It will normally have a positive value - a cost function should
be interpreted as having this much cost. Each of the extended
amounts are likewise representing profit or cost.
NOTE: There should be no artificial variables (!) in the
solution set unless the activity level of that variable is
zero. If positive, the problem is considered infeasible.
[ALTERNATE OPTIMA]
ALTERNATE OPTIMA, or ALT OPT, indicates that a variable not in
the solution set was qualified to be so. Its shadow price will
necessarily be zero. To force this variable into the solution
set, scan over to the range analysis for that variable.
Altering that variable's input to exceed that range by a small
amount will cause the alternate variable to most likely enter
the solution (solve the problem again). Additionally, re-
arranging variable or constraint order may cause the alternate
to enter the solution. Best, though, is to use a GTE inequal-
ity at the level required for that variable.
If the LP problem is found to be unbounded, the variable that
is responsible is indicated by UNB in the ALT OPT column.
18
LP OPERATIONS MANUAL --------------------------------------
NOTE: If after the first run, you wish to FORCE an alternate
optimum into the solution, DO NOT use an equality constraint.
Instead, use a >= inequality. E.g., X22 is ALT OPT - use
CONADD X22 >= 50 as a new constraint, not CONADD X22 = 50.
[ACTIVITY LEVEL]
Activity level is the value that a variable is to take in order
to achieve the optimal profit (or cost). Blank activity levels
should be interpreted as being zero. The activity level of
FUNCTION in the solution section should be interpreted as the
optimal profit or cost evaluation of the objective function.
It is normally positive.
[SHADOW PRICE]
Shadow prices fall into two categories.
One category indicates the rate of change in the objective
function evaluation if an activity that is not in the solution
set is introduced in the solution anyway. This marginal cost
represents the amount by which that activity, or variable, is
'too expensive' to be included in the solution set. This
category is attributable to the decision variables in the
VARIABLE SUMMARY.
The other category indicates the rate of change in the objec-
tive function evaluation when the RHS value of a constraint
changes. This marginal cost represents the amount by which the
objective function value will vary with changes in the RHS.
This category is attributable to the constraints (and the slack
and surplus variables in the VARIABLE SUMMARY) in the CON-
STRAINT SUMMARY.
Shadow prices are valid only over that variable/constraint's
range of optimality.
[UNUSED CAPACITY]
The unused capacity in the constraint summary of the analysis
section represents the amount of left-over resource for that
LTE constraint. It is included in the solution set as a
slack variable.
19
LP OPERATIONS MANUAL --------------------------------------
[EXCESS DEMAND]
The excess demand in the constraint summary of the analysis
section represents the amount of over-produced requirement for
that GTE constraint. It is included in the solution set as a
surplus variable.
[RANGE ANALYSIS]
Range analysis, also called sensitivity analysis, gives the
user useful information on the sensitivity of the data used
in the problem. Since accurate data may be expensive to
obtain, a model using the best available data can be used
initially. The analysis section can then be used to determine
which data are the most sensitive. These can then be further
researched.
Range analysis is performed on each of the variables and
constraints. For each variable, its input coefficient is
analyzed to see over which range of values it may take while
not altering the solution set, everything else remaining the
same.
Likewise for each constraint, except its RHS value is analyzed.
Additionally, the variable ENTERING (variable EXITING for
constraints) the basis (solution set) when a range is exceeded
is shown.
This variable may or may not be part of the final solution set,
since additional iterations of the simplex algorithm may be
needed.
[DEGENERATE]
If there are redundant constraints in a problem, it is possible
that a degenerate solution may develop (if so, DEGENERATE will
be displayed on the screen). Degeneracy in itself does not
pose any problems, usually. It may, however, lead to a problem
known as cycling. Cycling, once developed, causes the computer
code to endlessly cycle with no improvement in the objective
function. Fortunately, this seldom occurs with real-world
problems. Altering the order of constraints or variables
usually corrects this problem, should it ever occur.
Another problem associated with degeneracy is when an ALT OPT
variable is forced into a succesive LP solution set by
using an equality (=) constraint. This constraint will
20
LP OPERATIONS MANUAL --------------------------------------
necessarily be redundant. Use an inequality (>=), instead.
Otherwise, the sensitivity analysis and shadow prices may be
grossly misstated. This problem is easily identified by: one,
an artificial(!) variable(s) will be in the solution set (at
zero) and two, a shadow price(s) will be grossly misstated (by
BIG-M). At this point, the equality constraint(s) with its
artificial (!) in the solution should be removed or changed to
an inequality (>=), and rerun. Degeneracy may occur even if
there are no redundant constraints.
[ABORTING]
Pressing Esc will have the following effect on LP. If LP
is:
PARSING DECLARATIONS, or
PARSING OBJECTIVE FUNCTION, or
PARSING CONSTRAINTS, or
OUTPUTTING SOLUTION pressing Esc will end the current problem,
or if:
OUTPUTTING MAP, or
OUTPUTTING TABLEAU, or
OUTPUTTING ANALYSIS pressing Esc will skip that particular
section, or if:
FINDING FEASIBLE SOLUTION, or
ADDING CUTPLANE, or
OPTIMIZING pressing Esc will cause LP to complete the
current simplex iteration as if it had found an optimal
solution.
Also available is an immediate abort key: <Ctrl><F1>. Upon
pressing this key combination, the entire LP session is
immediately aborted to DOS.
[SPREADSHEET]
LP allows the user to use LOTUS 1-2-3 or Symphony as a tool
to create LP data files. 1-2-3 versions through 2.01 and
Symphony through 1.1 can be directly read by LP. Future
versions of these spreadsheets may or may not produce compat-
ible file ID bytes. If a version later than those above is
used and LP reports an unknown LOTUS file format (unlikely),
save the 1-2-3 data in WKS, WK1, WRK, WR1 format. These
formats are known to be compatible with LP.
If the OUTPUT: specifies that output should be sent to a file
with an extension of WKS, then LP will format the analysis
and solution sections in LOTUS 1-2-3 version 1A format. This
21
LP OPERATIONS MANUAL --------------------------------------
file can be read by many spreadsheet programs, not just those
of LOTUS. The listings, matrix map, and tableaux will also be
output, but in ASCII format. If there are no errors, this
ASCII output will be overwritten by the analysis and solution
sections in WKS format.
[LPEDIT.COM]
To put a linear program in LP readable form requires an
ASCII text editor (or Lotus, et. al). Many word processors
also allow their output to be in ASCII and even some spread-
sheets programs can 'print' to an ASCII file.
Included with the LP package is a full-screen text editor
that allows basic text editing. To edit a new file, include
the new filename on the command line after LPEDIT, or, use an
existing one to edit an old file. E.g.,
C>LPEDIT EXAMPLE.LP
Commands are issued via the F keys and are displayed on the
last line. The maximum file size is 64KB. Maximum editing
width of a line is 248 columns. The keypad keys are used to
position the cursor and <Ctrl> left/right-arrow is used to pan
left and right. A minimum of 68K of free RAM is needed by the
editor. If 132K is available, print/mark/cut/paste are
functional.
NOTE: The F3-PRINT key is used to print marked text only.
[VIRTUAL MEMORY]
For problems too large for available RAM, use the /VM command
line switch. This will write the matrix to disk and call it
in as needed. The speed penalty will be very dependent on the
speed of your virtual storage device. If you have a RAM disk
in extended or expanded RAM, expect the problem to take 3
times longer than if you had that RAM available to DOS. Not
bad when you consider the problem could not be solved at all
without this feature.
If you use this mode, INTEGER, and MIXED will be turned off.
Tableaux can only be printed by using LPDUMP.EXE, and only if
TABLEAU was YES.
LP will use the DOS variable TMP to locate $LP_261.VMM,
22
LP OPERATIONS MANUAL --------------------------------------
and, if TABLEAU is YES, $LP_261.DIC. If TMP is not defined,
the current directory is used.
[LPDUMP.EXE]
This program will dump the final tableau of problems solved
with the /VM switch to a WKS file. TABLEAU must have been YES.
LPDUMP will use the $LP_261.VMM & $LP_261.DIC files to create
a Lotus 1-2-3 1A WKS spreadsheet, readable by most spreadsheet
programs.
The number of columns that your spreadsheet can handle should
be at least the value of RHS + 1 (RHS can be found in the
$LP_261.DIC file).
LPDUMP.EXE uses the TMP DOS variable to locate the VMM, DIC, &
WKS files or will use the current directory if TMP is not
defined. E.g.,
C>LPDUMP
will use $LP_261.VMM, $LP_261.DIC, $LP.WKS or,
C>LPDUMP filename
will use filename.VMM, filename.DIC, filename.WKS. You are
given the chance to alter any of the pathnames in LPDUMP.
23
LP OPERATIONS MANUAL --------------------------------------
- $LP_261.VMM
$LP_261.VMM is the virtualized matrix. Its format is:
x=don't care
OFC=obj func coef
m=RHS-1
x OFC1 OFC2 OFC3 ... OFCm Z Z=obj func value
B1 MC11 MC12 MC13 ... MC1m RHS1 RHS=right-hand side
B2 MC21 MC22 MC23 ... MC2m RHS2 MC=matrix coefficient
B3 MC31 MC32 MC33 ... MC3m RHS3 B=basis
Bn MCn1 MCn2 MCn3 ... MCnm RHSn n=# of constraints
It's streamed without any delimiters. Each value is an IEEE
8-byte double-precision float. The matrix is in row-major
order. To determine where each row begins use this formula:
FirstByteOfRow(i) = (i-1)*((RHS + 1)*8) where i is 1-based.
RHS can be found in $LP_261.DIC.
- $LP_261.DIC
$LP_261.DIC is only created if TABLEAU is YES. It is an ASCII
text file describing the LP problem. CON is number of con-
straints (rows) not including the objective function RHS is the
right-hand side column of the matrix VAR is the number of
decision variables LTE is the number of less-than-or-equal to
constriants GTE is the number of greater-than-or-equal to
constriants EQU is the number of equal to constriants. The
names of the variables in the basis (Bn above) follow BASIS.
The column names (OFCm above) follow COLUMN NAMES.
[ERRORS]
- FILE
File errors occur when LP is unable to access either the
input data file or create the output file. These type errors
cause LP to abort to the next file in the queue.
FILE NOT FOUND indicated file was not found
CANNOT OPEN INPUT indicated file cannot be opened (bad name)
CANNOT OPEN OUTPUT indicated file cannot be opened (bad name)
24
LP OPERATIONS MANUAL --------------------------------------
- DECLARATION
Declaration errors occur when LP is unable to properly
format the model as given. Since an output channel may not
have been assigned, error reporting is done on the disposition
line of the display screen. If a single error was detected,
the error itself, followed by its code, is listed on this line.
If, however, more than one error was detected, the error
message *** MULTIPLE DECLARATION ERRORS is listed followed by a
code indicating the errors. LP then aborts to the next file
in the queue. The error codes are:
00000001 VAR: NOT FOUND In the case of multiple errors,
00000010 LTE: NOT FOUND combinations of these codes will
00000100 GTE: NOT FOUND be output, e.g., 00001001 means
00001000 EQU: NOT FOUND that VAR: and EQU: were not found
00010000 FUNCTION: NOT FOUND in the LP data file.
00100000 MAX: or MIN: NOT FOUND
01000000 UNKNOWN CHARACTER IN DECLARATION
- OBJ FUNCTION
Objective function errors occur when LP is unable to
properly read and interpret the objective function. Since an
output channel will have been made by this point, the error
report is sent to the output. The display screen will show the
error message *** OBJECTIVE FUNCTION ERROR and the error code
and LP aborts to the next file in the queue. The error
codes are:
00000001 FORMULATION BAD NEAR VARIABLE too many operators(+/-)
00000010 UNKNOWN VARIABLE # indicated variable not expected
00000100 DUPLICATE VARIABLE # indicated variable used > once
Multiple errors are not detected.
- CONSTRAINT
Constraint errors occur when LP is unable to properly read
and interpret a constraint. Since an output channel will have
been made by this point, the error report is sent to the
output. The display screen shows the error message ***
CONSTRAINT ERROR and the error code and LP aborts to the
next file in the queue. The error codes are:
25
LP OPERATIONS MANUAL --------------------------------------
00000001 FORMULATION BAD too many operators (+/-)
00000010 UNKNOWN VARIABLE indicated variable not in FUNCTION:
00000100 DUPLICATE NAME indicated name used more than once
00001000 ILLEGAL CONSTRAINT NAME indicated name is illegal
00010000 LTE: count does not match declaration
00100000 GTE: count does not match declaration
01000000 EQU: count does not match declaration
10000000 MATRIX ALLOCATION OVERRUN LTE:+GTE: does not match
- 123 READ
When input is taken from a LOTUS file the following errors may
occur. These cause LP to abort to the next file in the
queue.
FILE NOT FOUND indicated file was not found
CANNOT OPEN INPUT indicated file cannot be opened (bad name)
UNKNOWN OR CORRUPT LOTUS FILE format unknown
- 123 WRITE
When ouput is sent to a WKS file the following error may occur.
This causes LP to abort to the next file in the queue.
CANNOT OPEN OUTPUT indicated file cannot be opened (bad name)
- INFEASIBLE MODEL
An INFEASIBLE MODEL error occurs if, at the time SIMPLEX
algorithm has found an optimal solution, an artificial variable
remains in the basis (solution set) at a positive activity
level. The next file is begun.
- UNBOUNDED MODEL
An UNBOUNDED MODEL error occurs if, at anytime in the SIMPLEX
algorithm, a variable can be introduced without bound. The
unbounded variable is identified by UNB in the ALT OPT column.
The next file is begun.
- ABORT
An ABORT error occurs if the user presses <Esc> to abort the
current problem that LP is solving or if the user presses
26
LP OPERATIONS MANUAL --------------------------------------
<Ctrl><F1> to immediately abort the LP session to the
system.
NOTE: If Esc is pressed in certain LP routines, that and
only that routine is exited early. Output will indicate this
if it occurs.
- RUN-TIME
A RUN-TIME error may occur under certain circumstances. These
are rare and in such an event, the LP session is aborted
to DOS.
6 NUMBER OVERFLOW 24 DEVICE TIMEOUT
7 OUT OF FAR MEMORY 25 DEVICE FAULT
11 DIVISION BY ZERO 27 OUT OF PAPER
14 OUT OF NEAR MEMORY 61 DISK FULL
71 DRIVE NOT READY
BASIC error numbers 52 to 76 are mostly hardware/disk related.
If a run-time error continues to occur see REPORT BUGS TO...
In addition to the RUN-TIME error number, the MODULE and LEVEL
at which the error occured are indicated on the disposition
line.
Run-time errors 7 and 14 are handled specially by LP. The
message OUT OF MEMORY will be displayed on the disposition line
with no MODULE or LEVEL report available. This generally means
that the problem you have specified is too large for the RAM
available.
[REPORT BUGS TO...]
Though LP has been through significant testing, minor bugs
may occur. If you experience any problems in using LP write
a complete description of the problem using BUG REPORT FORM
form as a guide. Also include a listing of the model, and if
possible, include the model on a floppy. Send this to:
Cornel Huth
ATTN: LP v2.61 REPORT
6402 Ingram Rd.
San Antonio, TX 78238
If necessary, call the BBS at (210)684-8065 (5pm-9am Central Time).
Assistance can be given only in the use of LP, not with the
linear programs/models that need to be formulated.
27
LP OPERATIONS MANUAL --------------------------------------
- BUG REPORT FORM
Program: LP v2.61 S/N: - Have you registered?
------- -- ----
Name:
--------------------------------------------------------
Addr:
--------------------------------------------------------
--------------------------------------------------------
--------------------------------------------------------
Phone: ( ) - ext. (only if collect)
------ --------- ------
Describe the problem, the circumstances of its happening, and
any errors reported by LP or the system. Include a descrip-
tion of the hardware and operating system and any other
software loaded in memory.
Any suggestions for improvement are welcome.
28
LP OPERATIONS MANUAL --------------------------------------
[SPECIFICATIONS]
MINIMUM REQUIREMENTS:
256K IBM-PC or compatible
DOS 2.1, one floppy drive
216,000 bytes free of system memory as reported by CHKDSK.EXE
The maximum problem size depends on available memory. Use this
formula to APPROXIMATE the number of K bytes needed by LP as
displayed in the upper-right corner of the display screen at
start-up (at 99%).
{[(VAR:+LTE:+GTE:+EQU:+2)*(LTE:+GTE:+EQU:+1)*8]+32000}/1024 = K
RAM needed
This is about 100 constraints and 400 variables, not counting
slacks. In /VM mode you will be able to solve much larger
problems, typically 1000 variables and 1000 constraints on 640K
machines (with adequate virtual storage and time).
The 8087/80287 math coprocessor will be used if available.
29
LP OPERATIONS MANUAL --------------------------------------
[INCLUDED FILES LIST]
README initial instructions & information
LP.EXE linear programming optimizer
LPHELP.EXE help program
LPDEMO.EXE demonstration program
LPDUMP.EXE dumps /VM final tableau to WKS
LPEDIT.COM full-screen ASCII text editor
LP.HLP data file used by the help program
LP.MAN LP Operations Manual
EXAMPLE.LP ASCII LP data file (simple example)
INTEGER.ILP ASCII LP data file (all-integer example)
MIXED.MLP ASCII LP data file (mixed-integer example)
EXAMPLE.WKS WKS LP data file (similar to EXAMPLE.LP)
PROJECT.ILP ASCII LP data file (project assignment example)
NRC85.WKS WKS LP data file (diet example)
NOTE: Be sure to make a working copy of this disk.
30
LP OPERATIONS MANUAL --------------------------------------
[SHAREWARE]
Shareware is a means that software authors have of releasing
their product without the overhead costs of marketing and
packaging. This gives users the option of obtaining a quality
product at a truly reasonable price. It also may be the only
means of obtaining software that is not available elsewhere, at
any price.
What this means is that users can use the product on a trial
basis without any obligation to purchase the software.
Generally, users may freely distribute the product to others
provided that any licensing agreement or stipulations that the
author has specified be followed.
The shareware concept does not allow a user to continue using
the product after the trial period unless the license
agreement has been fulfilled or otherwise been given permission
by the author.
************************* NOTICE ******************************
All LP *.EXE programs in the INCLUDED FILES LIST are the
sole property of Cornel Huth and are Copyright 1988-1993 by
Cornel Huth.
- LICENSE AGREEMENT
USAGE: LP may be used on a trial basis for 30 days.
After this, the user promises to fulfill this license agreement
or discontinue using LP. By using LP you agree to abide
by this LICENSE AGREEMENT.
FULFILLMENT: A limited license for using LP on a single
computer may be purchased for $50.00. Site licenses are
available. After receiving payment, a current, registered
version and receipt of payment is sent.
DISTRIBUTION: LP may be distributed without the author's
permission only if the following three stipulations are
followed:
1. The LP package must be distributed complete, including
ALL files listed in INCLUDED FILES LIST.
2. The LP package CANNOT be sold for profit. Recovery of
costs associated with distribution is allowed (NO PROFIT).
3. ONLY the SHAREWARE version of the LP package may be
distributed.
31
LP OPERATIONS MANUAL --------------------------------------
- REGISTRATION FORM (Use !ORDER.FRM on the distribution disk)
Name of licensee:
-----------------------------------------
Amount paid: $ ($50.00 ea. Site licenses available)
--------- (CHECK/MONEY ORDER, US DOLLARS/US BANK)
Comments:
-----------------------------------------------------
-----------------------------------------------------
Contact: Phone:( ) -
---------------------- ---- -----------
Would you like to be added to our mailing list?
--------------
Mail to:
-----------------------------------------------------
-----------------------------------------------------
-----------------------------------------------------
-----------------------------------------------------
Send payment to:
Cornel Huth
ATTN: LP v2.61 REGISTRATION
6402 Ingram Rd.
San Antonio, TX 78238
32
LP OPERATIONS MANUAL --------------------------------------
[TRADEMARKS]
* Microsoft, QuickBASIC, and Excel are registered trademarks of
Microsoft Corp.
* Lotus, 1-2-3, Symphony are registered trademarks of Lotus
Development Corp.
* VP-PLANNER is a registered trademark of Paperback Software
International
* IBM is a registered trademark of International Business
Machines Corp.
[DISCLAIMER]
By using this software you, the user, agree that any and all
problems or errors made by or caused by this software is the
sole responsibilty of you, the user.
33
